package org.aplombh.java.awcing.basic.dp.linearDP;

import java.io.*;
import java.util.ArrayList;

/**
 * 给定 n 个长度不超过 10 的字符串以及 m 次询问，每次询问给出一个字符串和一个操作次数上限。
 * <p>
 * 对于每次询问，请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
 * <p>
 * 每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
 * <p>
 * 输入格式
 * 第一行包含两个整数 n 和 m。
 * <p>
 * 接下来 n 行，每行包含一个字符串，表示给定的字符串。
 * <p>
 * 再接下来 m 行，每行包含一个字符串和一个整数，表示一次询问。
 * <p>
 * 字符串中只包含小写字母，且长度均不超过 10。
 * <p>
 * 输出格式
 * 输出共 m 行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。
 * <p>
 * 数据范围
 * 1≤n,m≤1000,
 * <p>
 * 输入样例：
 * 3 2
 * abc
 * acd
 * bcd
 * ab 1
 * acbd 2
 * 输出样例：
 * 1
 * 3
 */
public class EditDistance_899 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();
        int n = Integer.parseInt(s.split(" ")[0]);
        int m = Integer.parseInt(s.split(" ")[1]);
        ArrayList<String> str = new ArrayList<>();
        EditDistance ed = new EditDistance();
        for (int i = 0; i < n; i++) {
            str.add(reader.readLine());
        }
        for (int i = 0; i < m; i++) {
            s = reader.readLine();
            String p = s.split(" ")[0];
            int limit = Integer.parseInt(s.split(" ")[1]);
            int res = 0;
            for (String st : str) {
                if (ed.solve(st, p) <= limit)
                    res++;
            }
            System.out.println(res);
        }
    }
}

class EditDistance {
    public static final int N = 1010;
    int[][] f = new int[N][N];

    public int solve(String a, String b) {
        char[] x = a.toCharArray();
        char[] y = b.toCharArray();
        int n = a.length();
        int m = b.length();

        for (int i = 0; i <= n; i++) {
            // 初始化 最多i步 -> 全部删除
            f[i][0] = i;
        }
        for (int i = 0; i <= m; i++) {
            // 初始化 最多i步 -> 全部新增
            f[0][i] = i;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 删除i或者删除j
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                // 上面情况或者两个不修改
                if (x[i - 1] == y[j - 1]) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                // 上面情况或者
                else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
            }
        }
        return f[n][m];
    }
}
